package com.peng.tree.extend;

public class MyIndexTree {

    private int N;
    private int[] tree;

    private int[] originArr;


    MyIndexTree(int[] arr) {

        N = arr.length;
        originArr = new int[N];
        tree = new int[N+1];
    }

    public void add(int pos, int val) {
        originArr[pos-1]+=val;
        while (pos < N) {
            tree[pos] += val;
            pos += pos & -pos;
        }
    }

    public void update(int pos, int val) {
        int add = val-originArr[pos-1];
        originArr[pos-1] = val;
        while (pos < N) {
            tree[pos] += add;
            pos += pos & -pos;
        }
    }

    public int sum(int pos) {
        int res=0;
        while (pos>0) {
            res+=tree[pos];
            pos -= pos & -pos;
        }
        return res;
    }

    public int sumLR(int L,int R){
        return sum(R)-sum(L-1);
    }


    public static void main(String[] args) {
        int[] arr= {1,2,3,4,5};
        MyIndexTree tree = new MyIndexTree(arr);
        for (int i = 1; i <= arr.length; i++) {
            tree.add(i,arr[i-1]);
        }

        tree.update(2,6);

        System.out.println(tree.sum(5));

        System.out.println(tree.sumLR(2,3));

    }


}
